<?php

header("Content-type: text/html; charset=utf-8");
include './function.php';
include './GlobalUniqueId.php';
include './WeightedRoundRobin.php';
include './BubbleSort.php';
include './BinarySearch.php';
include './Random.php';
include './BitOperation.php';
include './Spl.php';
include './qrcode/phpqrcode/qrlib.php';
include './phpanalysis/phpanalysis.class.php';
include './list/Node.php';
include './list/SinglyLinkedList.php';
include './list/DoublyLinkedList.php';
include './list/CircularLinkedList.php';


$start_time = microtime(true);

//$a1 = 50;
//$a2 = -50;
//p(decbin(-50));
//p(decbin($a2));
//p(mb_strlen(decbin($a2)));
//die;
//p($a2);
//p(base_convert($a1, 10, 2));
//pp(base_convert($a2, 10, 2));
//$user_suf_arr = [];
//for ($i = 1; $i <= 100000; $i++) {
//
//    // 随机一个数值 user后缀
//    $user_suf = mt_rand(1, 2000000);
//    // 如果在数组中
//    if (in_array($user_suf, $user_suf_arr)) {
//        echo '重复，回滚' . PHP_EOL;
//        // 回滚
//        $i--;
//        continue;
//    }
//    $user_suf_arr[] = $user_suf;
//
//    $user[$i] = ['name' => 'user' . $user_suf, 'age' => mt_rand(1, 100), 'gender' => mt_rand(1, 2),];
//    $uid_index_arr[$user_suf] = $i;
//}
//$user = json_encode($user);
//file_put_contents('./user.json', $user);
//file_put_contents('./user.index.json', json_encode($uid_index_arr));
//$begin_time = microtime(true);
//// 读取数据
//$user = file_get_contents('./user.json');
//$user = json_decode($user, true);
//// 读取索引
//$index = file_get_contents('./user.index.json');
//$index = json_decode($index, true);
//// 假如很短时间内500个人并发查询
//// 查找同一个用户名不会有缓存，所以不用考虑缓存影响速度的问题
//for ($i = 1; $i <= 500; $i++) {
//    $suf = substr('user1948829', 4);
//    // 在索引文件中查找对应关系
//    $_index = $index[$suf];
//    $_user = $user[$_index];
//    echo $_user['age'] . PHP_EOL;
//}
//$end_time = microtime(true);
//echo '耗费时间' . ( $end_time - $begin_time ) . PHP_EOL;
//pp($start_time);
//$tt = '5c4138ef4';
//p(mb_strlen($tt));
//pp($start_time);
//$res = GlobalUniqueId::CreateBasicsUid(1);
//$rr = '201901100011475487669';
//pp(mb_strlen($rr));
//$tr = uniqid();
//$rr =  Random::machineRandom();
//p(mb_strlen($rr));
//pp($rr);
//$str = '123456789';
//pp(mb_substr($str, -4, 4));
//$rr = Random::BasicsRandom();
//p(mb_strlen($rr));
//pp($rr);
//for ($i = 0; $i <= 100; $i++) {
//    $rr = Random::getRandomNumber();
//    p(mb_strlen($rr));
//    p($rr);
//}
//die;
//$oo = GlobalUniqueId::CharacterToNumber($tr);
//p($tr);
//pp($oo);
//$tt = GlobalUniqueId::CreateBasicsUid(1);
//p(mb_strlen($tt));
//pp($tt);
//pp(microtime(true));
//$rr = GlobalUniqueId::microtime_format('Y-m-d H:i:s x', microtime(true));
//pp($rr);
//轮训算法
//命中测试比例
//$arr = array(
//    array('id' => 'A', 'weight' => 2),
//    array('id' => 'B', 'weight' => 3),
//    array('id' => 'C', 'weight' => 5),
//);
//$arr = array(
//    array('id' => 'A', 'weight' => 2),
//    array('id' => 'B', 'weight' => 3),
//    array('id' => 'C', 'weight' => 6),
//    array('id' => 'D', 'weight' => 6),
//    array('id' => 'E', 'weight' => 4),
//);
//$weight = new WeightedRoundRobin($arr);
//$a = 0;
//$b = 0;
//$c = 0;
//$d = 0;
//$e = 0;
//for ($j = 0; $j < 100; $j++) {
//    $weightInfo = $weight->getWeight();
////    print_r($weightInfo);
//    echo $weightInfo['id'] . '----------------------weight:' . $weightInfo['weight'] . '<br/>';
//    if ($weightInfo['id'] == 'A') {
//        $a++;
//    }
//    if ($weightInfo['id'] == 'B') {
//        $b++;
//    }
//    if ($weightInfo['id'] == 'C') {
//        $c++;
//    }
//    if ($weightInfo['id'] == 'D') {
//        $d++;
//    }
//    if ($weightInfo['id'] == 'E') {
//        $e++;
//    }
//}
//echo 'A:' . $a . '<br/>';
//echo 'B:' . $b . '<br/>';
//echo 'C:' . $c . '<br/>';
//echo 'D:' . $d . '<br/>';
//echo 'E:' . $e . '<br/>';
//exit;
//$array = array(0 => 'blue',  2 => 'green', 3 => 'red');
//
//$key = array_search('red', $array);
//
//pp($key);
//$arr = [6, 4, 7, 2, 9, 8, 1, 6, 4, 7, 2, 9, 8, 1];
//
//$rr = BubbleSort::BetterBubbleSort($arr);
//p($rr);
//$rr = BinarySearch::BasicBinarySearch($arr, 8);
//pp($rr);
//$a = 8;
//p(base_convert($a, 10, 2));
//$b = 4;
//p(base_convert($b, 10, 2));
//p($a << $b);
//p(base_convert(128, 10, 2));
//pp(ini_get('Architecture'));
//p(BitOperation::SystemDigit());
//$str = '11111111111111111111111111111111';
//$tt = BitOperation::Format($str);
//p($tt);
//$str = "Hello World";
//echo str_pad($str,30,".");
//die;
//$r = 0;
//$tt = decbin($r);
//$tt = BitOperation::Format($tt);
//p($tt);
//计算一个十进制数转换为二进制数中‘1’的个数
//例如十进制11 = 二进制1011，则结果是3个1
//解题思路：利用 n & (n - 1) 可以将最后一个1变0
//xxxx1000 & (xxxx1000 - 1) = xxxx1000 & xxxx0111 = xxxx0000
// 1011 & (1011 - 1) = 1011 & 1010 = 1010
//直到最后一个1被与为0，得出结果
//p(-2%3);
//$a1 = '0b' . decbin(3);
//pp(~3);
//$a2 = '0b' . decbin(2);
//p($a1);
//p($a2);
//p(bindec($a1));
//$rr = bcadd($a1, $a2);
//pp($rr);
//
//$y = ~$tt;
//pp($y);
//$t = bcadd('1111111111111111111111111111111111111111111111111111111', '222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222');
//pp(gettype($t));
//pp(bcadd('1111111111111111111111111111111111111111111111111111111', '222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222'));
//$tt = -555;
//p(decbin($tt));
//$tt = BitOperation::InverseCode($tt);
//p($tt);
//printf('%064b',$tt);
//$tt = -1;
//p(decbin($tt));
//$t = BitOperation::OriginalCode($tt);
//$a = 7;
//$b = 8;
//pp(BitOperation::average($a, $b));
//BitOperation::swap($a, $b);
//p($a);
//pp($b);
//p(base_convert($a, 10, 2));
//p(base_convert($b, 10, 2));
//p(BitOperation::DecimalToBinary($a));
//p(BitOperation::DecimalToBinary($b));
//p($a & $b);
//p(($a & 0xFFFF) && !($a & 0x8000));
//p(PHP_INT_MAX);
//p(PHP_FLOAT_MAX);
//$max = 1 << 31;
//p($max);
//p(1 >> 31);
//pp($max + 1);
//p(base_convert(0x8000, 16, 2));
//pp(base_convert(0x8000, 16, 2));
//$t = BitOperation::IntAdd($a, $b);
//$t = BitOperation::abs($a);
//$t = BitOperation::isNegative($a);
//pp($a>>31);
/*
 * 双向链表
 */
//$SplDoublyLinkedList = new SplDoublyLinkedList();
//
//$SplDoublyLinkedList->push('hiramariam');
//$SplDoublyLinkedList->push('maaz');
//$SplDoublyLinkedList->push('zafar');
////$s = $SplDoublyLinkedList->serialize();
////$SplDoublyLinkedList->isEmpty()
//p($SplDoublyLinkedList->top());
//pp($SplDoublyLinkedList);
//$s = new SplObjectStorage();
//
//$o1 = new StdClass;
//$o2 = new StdClass;
//$o3 = new StdClass;
//
//$s->attach($o1);
//$s->attach($o2);
//
//var_dump($s->contains($o1));
//var_dump($s->contains($o2));
//var_dump($s->contains($o3));
//
//$s->detach($o2);
//
//var_dump($s->contains($o1));
//var_dump($s->contains($o2));
//var_dump($s->contains($o3));
//trait foo {
//    
//}
//
//class bar {
//
//    use foo;
//}
//
////print_r(class_uses(new bar));
//print_r(class_uses('bar'));
//$value = 'http://www.baidu.cn'; //二维码内容 
//$r = QRcode::png($value);
//初始化类
//pp(base_convert(0xFE, 16, 10));
//pp(chr(0xFF).chr(0xFE));
//$str = '民进党此时大声嚷嚷，目的正是为了表态，这是对中国大陆的一种抗议，也是在2020“大选”前为两岸政策定调。';
//$do_fork = $do_unit = true;
//$do_multi = $do_prop = $pri_dict = false;
//PhpAnalysis::$loadInit = false;
//$pa = new PhpAnalysis('utf-8', 'utf-8', $pri_dict);
//
////载入词典
//$pa->LoadDict();
//
//pp($pa->mainDicFile);
//
////执行分词
//$pa->SetSource($str);
//$pa->differMax = $do_multi;
//$pa->unitWord = $do_unit;
//
//$pa->StartAnalysis($do_fork);
//
//$okresult = $pa->GetFinallyResult(' ', $do_prop);
//p($okresult);
//$end_time = microtime(true);
//pp('运行时间为' . (sprintf('%0.4f', $end_time - $start_time)) . '毫秒');
class Hero {

    public $pre = null; //表示指向前一个节点的引用
    public $no;
    public $name;
    public $nickname;
    public $next = null; //表示指向后一个节点的引用

    public function __construct($no = '', $name = '', $nickname = '') {
        $this->no = $no;
        $this->name = $name;
        $this->nickname = $nickname;
    }

    //添加hero，这里我们会构建一个双向链表
    //这里使用了静态函数
    //添加英雄，把添加时是空链表和不是空链表的情况，合并到一起了
    public static function addHero($head, $hero) {
        //$head头节点不能动
        //$cur为辅助节点，让$cur来穿针引线
        $cur = $head;
        //isExist 假设英雄不存在
        $isExist = FALSE; //这是一个标志位
        //首先看看目前的这个链表是不是空的
        //当还有英雄的时候，$cur指向的$head节点的next属性必然为null，因为现在只有head节点，还没有添加英雄
        //如果是空链表就直接加入
        //怎样把空链表和普通链表并和在一起呢？

        while ($cur->next != null) { //只要$cur->next不等于null，就说明没有到队尾
            if ($cur->next->no > $hero->no) { //说明位置找到了，则说明$hero要加在$cur的后面
                break;
            } else if ($cur->next->no == $hero->no) {
                $isExist = TRUE;
                echo'<br/>不能添加相同的编号';
            }
            //继续下一个
            $cur = $cur->next;
        }

        //退出该while循环时候，我们只需要把$hero添加到$cur后面即可，（队尾）
        //说明还没有这个排名，可以添加，并可以和上面的空链表判断合并
        if (!$isExist) { //如果不存在就添加，因为在上面break跳出的时候，就说明找到了，跳出的时候$isExist为假，则!$isExist为真
            //添加，有点麻烦
            //当你添加的人物就在最后，比如现在只有1号英雄，再添加一个5号英雄，肯定是添加在1号英雄的后面
            //这里加上if判断，会更稳健型些
            if ($cur->next != null) {
                $hero->next = $cur->next;
            }
            $hero->pre = $cur;
            if ($cur->next != null) {
                $cur->next->pre = $hero;
            }
            $cur->next = $hero;
        }
    }

    //删除某位英雄，现在不需要辅助节点了
    public static function delHero($head, $herono) {
        //我们不使用辅助节点了
        //先找到$head
        //$head不能动
        //直接让$cur指向下一个，$head->next就是具体的英雄了，当然还要先判断，$cur->next是不是空，要是空，就是光有head了，也没有要删除的了
        $cur = $head->next;
        $isFind = false; //先搞个标志位
        while ($cur != null) {
            if ($cur->no == $herono) {
                //找到了，就置为true，并跳出
                $isFind = true;
                break;
            }

            //如果上面的if没有找到，就不停的向下走
            $cur = $cur->next;
        }

        if ($isFind) {
            //当$isFind为真的时候，就说明找到了
            //执行删除
            //自我删除
            //这里考虑了要删除的英雄在末尾的时候情况
            if ($cur->next != null) {
                $cur->next->pre = $cur->pre;
            }
            $cur->pre->next = $cur->next;
            echo '<br/>要删除的英雄编号是' . $cur->no;
        } else {
            echo'<br/>要删除的英雄没有';
        }
    }

    //遍历显示双向链表，显示所有英雄的函数
    public static function showHero($head) {
        //上来线做一个辅助指针，穿针引线
        $cur = $head->next; //头本来就是空的，这样就输出打印的时候，不输出头了
        //$cur=$head; 如果是这样，每次输出的时候会输出：编号= 名字= 外号=  把头也输出了

        while ($cur->next != null) { //为空就说明到队尾了
            echo'<br/>编号=' . $cur->no . '名字=' . $cur->name . '外号=' . $cur->nickname;
            //继续下移一步
            $cur = $cur->next;
        }

        //当退出while的时候，$cur就指向了最后的那个节点了
        //要是不输出，就会少一个人，少队尾的那个人
        echo'<br/>编号=' . $cur->no . '名字=' . $cur->name . '外号=' . $cur->nickname;
    }

}

//创建一个头节点
$head = new Hero();
//创建一个英雄
$hero = new Hero(1, '宋江', '及时雨');

//静态方法的调用
Hero::addHero($head, $hero);

$hero = new Hero(2, '卢俊义', '玉麒麟');
Hero::addHero($head, $hero);

$hero = new Hero(6, '林冲', '豹子头');
Hero::addHero($head, $hero);

$hero = new Hero(3, '吴用', '智多星');
Hero::addHero($head, $hero);

$hero = new Hero(56, '孙二娘', '母夜叉');
Hero::addHero($head, $hero);
echo '<br/>英雄排行榜.....';
//显示
Hero::showHero($head);

echo'<br/>';
echo '<br/>删除后的英雄排行榜.....';
Hero::delHero($head, 3);
Hero::showHero($head);

echo'<br/>';
echo'<br/>下面测试删除最前面的和最后面的英雄<br/>';
echo '<br/>删除后的英雄排行榜.....';
Hero::delHero($head, 1);
Hero::showHero($head);

echo'<br/>';
echo '<br/>删除后的英雄排行榜.....';
Hero::delHero($head, 56);
Hero::showHero($head);



//单链表
$head = new Node([]);

$SinglyLinkedList = new SinglyLinkedList();
$node1 = new Node(['id' => 2, 'name' => '李1']);
$SinglyLinkedList->push($head, $node1);

//pp($SinglyLinkedList->getList());
$node2 = new Node(['id' => 5, 'name' => '李5']);
$SinglyLinkedList->push($head, $node2);

$node3 = new Node(['id' => 7, 'name' => '李7']);
$SinglyLinkedList->push($head, $node3);

$SinglyLinkedList->pop($head);
pp($head);


final class Node {

    public $data;
    public $next = null;

    public function __construct($data) {
        $this->data = $data;
    }

}

final class LinkedList {

//    //从链表尾部压入一个节点，节点自动维护，不需要要像main方法那样自己维护
    public function push(Node $head, Node $Node) {

        while ($head->next != null) {
            $head = $head->next;
            p($head);
        }
//        pp($head);
        $head->next = $Node->next;
        $head->next = $Node;
        p($head);
        
    }

    //从链表尾压出一个节点
    public function pop(Node $head) {
        $current = $head; //让$current指向$head;
        while ($current->next != null) {
            //提前查找链表尾部是否为空，为空就是尾部，吧当前节点的next复制问NULL，就是尾部元素干掉
            if ($current->next->next == null) {
                break;
            }
            $current = $current->next;
        }
        $current->next = null;
    }

}

$head = new Node([]);
$a = new Node(['a']);
$b = new Node(['b']);
$c = new Node(['c']);
$d = new Node(['d']);

$LinkedList = new LinkedList();
$LinkedList->push($head, $a);
$LinkedList->push($head, $b);
$LinkedList->push($head, $c);
$LinkedList->push($head, $d);
$LinkedList->pop($head);
pp($head);



$head = new BasicNode(null, []);
$a = new BasicNode(1, ['a']);
$b = new BasicNode(5, ['b']);
$c = new BasicNode(8, ['c']);
$d = new BasicNode(99, ['d']);
$e = new BasicNode(66, ['e']);

//if ($head->next->index > 1) {
//    pp('大于');
//} else {
//    pp('小于');
//}

$DoublyLinkedList = new DoublyLinkedList();
$DoublyLinkedList->add($head, $b);
//pp($head);
$DoublyLinkedList->add($head, $a);
//pp($head);
$DoublyLinkedList->add($head, $d);
$DoublyLinkedList->add($head, $e);

$DoublyLinkedList->add($head, $c);

//$DoublyLinkedList->update($head, 5, ['2312321']);
$DoublyLinkedList->delete($head, 99);
pp($head);